// #include <stdio.h>
// #include <stdbool.h>
// #include"windows.h"
//
// #define MAX_SIZE 100 // 顺序表的最大容量
//
// // 顺序表结构体
// typedef struct {
//     int data[MAX_SIZE]; // 数据存储数组
//     int length;         // 当前顺序表长度
// } SeqList;
//
// // 初始化顺序表
// void InitSeqList(SeqList* L) {
//     L->length = 0; // 初始长度为 0
// }
//
// // 向顺序表中插入元素
// bool Insert(SeqList* L, int index, int value) {
//     if (index < 0 || index > L->length || L->length >= MAX_SIZE) {
//         printf("插入位置不合法或顺序表已满！\n");
//         return false;
//     }
//     for (int i = L->length; i > index; i--) {
//         L->data[i] = L->data[i - 1]; // 元素后移
//     }
//     L->data[index] = value; // 插入新元素
//     L->length++; // 长度加 1
//     return true;
// }
//
// // 顺序查找（不带哨兵）
// int SequentialSearch(SeqList* L, int target) {
//     for (int i = 0; i < L->length; i++) {
//         if (L->data[i] == target) {
//             return i; // 找到目标，返回索引
//         }
//     }
//     return -1; // 未找到目标，返回 -1
// }
//
// // 顺序查找（带哨兵）
// int SequentialSearchWithSentinel(SeqList* L, int target) {
//     if (L->length >= MAX_SIZE) {
//         printf("顺序表已满，无法设置哨兵！\n");
//         return -1;
//     }
//
//     int lastElement = L->data[L->length - 1]; // 保存最后一个元素
//     L->data[L->length - 1] = target; // 将最后一个元素替换为哨兵
//
//     int i = 0;
//     while (L->data[i] != target) {
//         i++;
//     }
//
//     L->data[L->length - 1] = lastElement; // 恢复最后一个元素
//
//     if (i < L->length - 1 || L->data[L->length - 1] == target) {
//         return i; // 找到目标，返回索引
//     } else {
//         return -1; // 未找到目标，返回 -1
//     }
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     SeqList L;
//     InitSeqList(&L);
//
//     // 向顺序表中插入元素
//     Insert(&L, 0, 3);
//     Insert(&L, 1, 5);
//     Insert(&L, 2, 2);
//     Insert(&L, 3, 8);
//     Insert(&L, 4, 1);
//     Insert(&L, 5, 9);
//     Insert(&L, 6, 4);
//
//     int target = 8; // 查找目标
//
//     // 不带哨兵的顺序查找
//     int index1 = SequentialSearch(&L, target);
//     if (index1 != -1) {
//         printf("不带哨兵：目标 %d 在顺序表中的索引是: %d\n", target, index1);
//     } else {
//         printf("不带哨兵：目标 %d 未找到！\n", target);
//     }
//
//     // 带哨兵的顺序查找
//     int index2 = SequentialSearchWithSentinel(&L, target);
//     if (index2 != -1) {
//         printf("带哨兵：目标 %d 在顺序表中的索引是: %d\n", target, index2);
//     } else {
//         printf("带哨兵：目标 %d 未找到！\n", target);
//     }
//
//     return 0;
// }